package com.salim.leetcode.$5;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: clevo
 * Date: 15-9-8
 * Time: 下午3:05
 * To change this template use File | Settings | File Templates.
 */
public class LongestPalindromic {

    //情况1 def|g|fed
    //情况2 def|ggggg|fed

    class MiddleString{
        int start = 0;
        int end = 0;
        MiddleString(int start,int end){
            this.start = start;
            this.end = end;
        }

        int getStart(){
            return start;
        }

        int getEnd(){
            return end;
        }
    }


    public String longestPalindrome(String s) {
        int maxCount = 0;
        int maxStart = 0;
        int maxEnd = 0;
        List<MiddleString> middleStringList = new ArrayList<MiddleString>();
        findMiddleString(s,middleStringList);
        for(MiddleString middleString:middleStringList){
            int start = middleString.getStart();
            int end = middleString.getEnd();
            int count = countPalindromeLength(s,start,end);
            if((count + end) - (start-count) >=maxCount){
                maxStart = start-count;
                maxEnd = end+count;
                maxCount = (count + end) - (start-count);
            }
        }
        return s.substring(maxStart,maxEnd+1);
    }


    public void findMiddleString(String s,List<MiddleString> middleStringList){
        int start = 0;
        int end = 0;
        boolean inDouble = false;
        if(s.length()==1){
            middleStringList.add(new MiddleString(0,0));
            return;
        }
        //因为题目要求必定有回文 长度2直接返回整个
        if(s.length()==2){
            middleStringList.add(new MiddleString(0,1));
            return;
        }

        //cccc这种第一次进来下标错误
        int i =1;
        if(s.charAt(i-1) == s.charAt(i) && i==1){
            i--;
        }
        for(;i<s.length();i++){
            //最后一个字符处理方式
            if(i==s.length()-1){
                if(inDouble){
                    middleStringList.add(new MiddleString(start,i));
                }
                return;
            }

            //情况2 def|ggggg|fed
            if(s.charAt(i) == s.charAt(i+1)){
                //第一次进入double
                if(!inDouble){
                    inDouble = true;
                    start = i;
                    end = i-1;
                }
                end++;
                continue;
            }
            //情况2结束 记录点并归零
            if(inDouble){
                middleStringList.add(new MiddleString(start,end+1));
                start = i;
                end = i;
                inDouble = false;
                i--;
                continue;
            }

            //情况1 def|g|fed
            if(s.charAt(i-1) == s.charAt(i+1)){
                middleStringList.add(new MiddleString(i,i));
                start = i+1;
                end = i+1;
                continue;
            }
        }
    }

    public int countPalindromeLength(String s,int start,int end){
        int count = 0;
        while (start-1 >= 0 && end+1 <= s.length()-1){
            if(s.charAt(start-1) == s.charAt(end+1)){
                count++;
                start--;
                end++;
            }else{
                break;
            }
        }
        return count;
    }

    public static void main(String[] args){
        LongestPalindromic lp = new LongestPalindromic();
        String str = "cabcdddddddddcba";
        System.out.println(lp.longestPalindrome(str));
        String a = "a";
        System.out.println(lp.longestPalindrome(a));
        String aa = "abba";
        System.out.println(lp.longestPalindrome(aa));
        String bb = "abb";
        System.out.println(lp.longestPalindrome(bb));
        String abcbe = "abcbe";
        System.out.println(lp.longestPalindrome(abcbe));
        String ccc = "cccc";
        System.out.println(lp.longestPalindrome(ccc));
        String abadd = "abadd";
        System.out.println(lp.longestPalindrome(abadd));
        String abadddddddaabbcbbaadddddddaba = "abadddddddaabbcbbaadddddddaba";
        System.out.println(lp.longestPalindrome(abadddddddaabbcbbaadddddddaba));

    }
}
